package com.cjm.algorithm.str;

public class Ti240422459 {
    public static void main(String[] args) {
        Ti240422459 ti240422459 = new Ti240422459();
        System.err.println(ti240422459.repeatedSubstringPattern("babbabbabbabbab"));
    }

    public boolean repeatedSubstringPattern(String s) {
        if (s.length() == 0) {
            return false;
        }
        int len = s.length();
        int[] next = new int[len];

        int i = 1, j = 0;
        next[0] = 0;
        while (i < len) {
            if (s.charAt(i) == s.charAt(j)) {
                next[i] = j + 1;
                i++;
                j++;
                continue;
            }
            if (j == 0) {
                next[i] = 0;
                i++;
                continue;
            }
            j = next[j - 1];
        }
        if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
            return true;
        }
        return false;
    }
}
